package org.laizili.solution.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

/**
 * <a href="https://leetcode-cn.com/problems/insert-delete-getrandom-o1/">380. O(1) 时间插入、删除和获取随机元素</a>
 * <p>
 * tags: 数组; 哈希表
 * </p>
 */
public class Problem380 {
    private static class RandomizedSet {
        Random random = new Random();
        // 将 val 映射到 list 下标
        HashMap<Integer, Integer> mapValToLoc = new HashMap<>();
        // 存储数据
        List<Integer> vals = new ArrayList<>();
        // 元素个数
        int size = 0;

        public RandomizedSet() {
        }

        public boolean insert(int val) {
            if (mapValToLoc.containsKey(val)) {
                return false;
            }
            vals.add(val);
            mapValToLoc.put(val, size);
            ++size;
            return true;
        }

        //数组+哈希表 完成O（1）删除
        // 易错点:
        //      mapValToLoc与vals 数据状态不同步
        public boolean remove(int val) {
            if (!mapValToLoc.containsKey(val)) {
                return false;
            }

            final Integer loc = mapValToLoc.remove(val); // 待删除元素下标
            size--;
            if (loc != size) { // 如果末尾元素不是待删除元素
                int movedVal = vals.get(size); // 末尾元素
                vals.set(loc, movedVal); // 移动末尾至loc位置
                mapValToLoc.put(movedVal, loc); // 更新为新下标loc
            }
            vals.remove(size); // O(1) 删除
            return true;
        }

        public int getRandom() {
            return vals.get(random.nextInt(size));
        }
    }

    public static void main(String[] args) {
        RandomizedSet set = new RandomizedSet();
        System.out.println(set.remove(0));
        System.out.println(set.remove(0));
        System.out.println(set.insert(0));
        System.out.println(set.getRandom());
        System.out.println(set.remove(0));
        System.out.println(set.insert(0));
    }
}
